/*

http://blog.csdn.net/v_JULY_v/article/details/6110269


*/


#include <iostream>
#include <string.h>
//#inlcude <cstdio>

using namespace std;

enum decreaseDir{kInit = 0, kLeft, kUp, kLeftUp};

/*
print the LCS
*/
void LCSPrint(int **LCSDirection,
	char *pStr1, char* pStr2, int row, int col);

/*
Get the length of the LCS
*/
int LCS(char* pStr1, char* pStr2)
{
	if(!pStr1|| !pStr2)
		return 0;
	
	int length1 = strlen(pStr1);
	int length2 = strlen(pStr2);
	
	if(!length1||!length2)
		return 0;
	
	int i, j;
	
	/*initate the matrix table*/
	int **LCSLength;
	LCSLength = (int**)(new int[length1]);
	for(i = 0;i<length1; i++)
		LCSLength[i] = (int *)new int [length2];

	for(i = 0; i < length1; i++)
		for(j = 0; j < length2; j++)
			LCSLength[i][j] = 0;
		
	/*initate the direction table*/
	int **LCSDirection;
	LCSDirection = (int**)(new int[length1]);
	for(i = 0;i<length1; i++)
		LCSDirection[i] = (int *)new int [length2];

	for(i = 0; i < length1; i++)
		for(j = 0; j < length2; j++)
			LCSDirection[i][j] = kInit;

	
	for(i = 0; i < length1; i++)
	{
		
		for(j = 0; j < length2; j++)
		{
			
			if(i == 0|| j == 0)
			{
				if(pStr1[i] == pStr2[j])
				{
					LCSLength[i][j] = 1;
					LCSDirection[i][j] = kLeftUp;
				}
				else
				{
					if(i > 0)
					{
						LCSLength[i][j] = LCSLength[i-1][j];
						//LCSLength[i][j] = 1;
						LCSDirection[i][j] = kUp;
					}
					if(j > 0)
					{
						LCSLength[i][j] = LCSLength[i][j-1];
						LCSDirection[i][j] = kLeft;
					}
				}
				
			}
			else if(pStr1[i] == pStr2[j])
			{
				LCSLength[i][j] = LCSLength[i-1][j-1] + 1;
				LCSDirection[i][j] = kLeftUp;
				
			}
			else if(LCSLength[i-1][j] > LCSLength[i][j-1])
			{
				LCSLength[i][j] = LCSLength[i-1][j];
				LCSDirection[i][j] = kUp;
			}
			else{
				LCSLength[i][j] = LCSLength[i][j-1];
				LCSDirection[i][j] = kLeft;
			}
			
			
		}
		
		
	}

	LCSPrint(LCSDirection, pStr1, pStr2, length1-1,length2-1);
	return LCSLength[length1-1][length2-1];
}

void LCSPrint(int **LCSDirection,
	char *pStr1, char* pStr2, int row, int col)
{
	//cout<<"print"<<endl;
	if(!pStr1|| !pStr2)
		return;
	
	int length1 = strlen(pStr1);
	int length2 = strlen(pStr2);
	
	if(length1 == 0 ||  length2 == 0 || !(row < length1 && col < length2) )
		return;	
		
	if(LCSDirection[row][col] == kLeftUp)
	{
		if(row > 0 && col > 0)
			LCSPrint(LCSDirection, pStr1, pStr2, row-1,col-1);
		cout<<pStr1[row]<<" ";
	}else if(LCSDirection[row][col] == kLeft)
	{
		if(col>0)
			LCSPrint(LCSDirection, pStr1, pStr2, row,col-1);
	}else if(LCSDirection[row][col] == kUp)
	{
		if(row>0)
			LCSPrint(LCSDirection, pStr1, pStr2, row-1,col);
	}
			
}


int main()
{
	char* pStr1 = "abcde";
	char* pStr2 = "acde";
	int length = LCS(pStr1,pStr2);
	cout<<endl;
	cout<<length<<endl;
	return 0;
}